/*-------------------------------------------------------------------------*/
/**
  @file		execrefine.c
  @author	Renaud Wanchoor
  @date	July 2004
  @version	$Revision: 2.28 $
  @brief	execution time uncoarsening 
  @update date	March 2007 by Xiaochen Wu
  
*/
/*--------------------------------------------------------------------------*/

#include "pagrid.h"
#include "execrefine_params.h"

static int  Refine (RefCtrl*);
static int  RefineKl(RefCtrl* ctrl);

/**
 * \brief execution time local refinement
 *
 * local refinement of a given partition of graph onto grid, this
 * refinement aims at decreasing the total execution time while
 * balancing the load among processors. No random numbers are used
 * the only way to use random numbers is to randomly place reassignments
 * with the same gain into the move heap. A possible solution to that would 
 * be to randomly scan the graph when building boundaries. This would add
 * some randomness but this would may not be significant.
 *
 *
 * \param graph application graph
 * \param grid computational grid
 * \param level level of uncoarsening
 * \param guide unused
 * \param info unused
 */

void execRefine(GraphType *g, GridType *n, int level, int *guide, PartInfoType *info){
  static int levels = -1;
  
  int i, from,to,nb_moves,moves,totnb_moves,loops,nbnds;  
  Mem       mem;
  Heap      pHeap,refHeap;
  RefCtrl   RCtrl;

  int     nnpro = n->npro;
  double* nexec = n->exec;
  
  /* prepare */
  MEM_Init(&mem);
    
  RCtrl.level       = level;
  RCtrl.guide       = guide;  
  RCtrl.heap        = &refHeap;
  RCtrl.pheap       = &pHeap;
  RCtrl.g 	    = g;
  RCtrl.n 	    = n;
  RCtrl.t           = 0;
  
  /* alloc */  
  RCtrl.procs       = U_malloc(nnpro,int,"execRefine error code 1.1\n");
  RCtrl.proref      = U_malloc(nnpro,vRefCont,"execRefine error code 1.2\n");
#if MOVE_ONCE
  RCtrl.mvtxs       = U_mallocset(RCtrl.g->nvtxs,int,0,"execRefine error code 1.3\n");
#endif
  RCtrl.bnds        = U_malloc(RCtrl.g->nvtxs,vRef,"execRefine error code 1.4\n");
  RCtrl.procon      = U_malloc(nnpro,int,"execRefine error code 1.5\n");
  
  nbnds             = VREF_Build(&RCtrl);  

  MEM_Need(&mem,nnpro,double);
  MEM_Need(&mem,nnpro,int);
  MEM_Need(&mem,nnpro,int);
  MEM_Need(&mem,MAX_KLMOVES,vRef);
  MEM_Need(&mem,8*nbnds/2,vRef*);
  MEM_Need(&mem,nnpro,double);
  HeapInit(&mem,&pHeap,nnpro);
  HeapInit(&mem,&refHeap,8*nbnds/2);
 
  MEM_Allocate(&mem);

  RCtrl.flow        = MEM_Request(&mem,nnpro,double);
  RCtrl.procs2      = MEM_Request(&mem,nnpro,int);
  RCtrl.procon2     = MEM_Request(&mem,nnpro,int);
  RCtrl.undo        = MEM_Request(&mem,MAX_KLMOVES,vRef);
  RCtrl.nb_undo     = 0;
  RCtrl.exec        = MEM_Request(&mem,nnpro,double);
  RCtrl.nrvtxs      = 0;
  RCtrl.rvtxs       = MEM_Request(&mem,8*nbnds/2,vRef*);
  
  /* init */
  if(levels == -1)
    levels = level;

  for(i=0;i<nnpro;i++)
    RCtrl.t += nexec[i]; 

  RCtrl.tmean = RCtrl.t/nnpro;
  RCtrl.tmax = 0;
  RCtrl.tmin = INFINITY;

  for(i=0;i<nnpro;i++){
    if(nexec[i] > RCtrl.tmax)
      RCtrl.tmax = nexec[i];
    if(nexec[i] < RCtrl.tmin)
      RCtrl.tmin = nexec[i];
  }

  RCtrl.im          = nnpro*RCtrl.tmax/RCtrl.t;
  RCtrl.imthreshold = IMTHRESHOLD(MAX_IM,levels,&RCtrl);  


/*  int *gadjidx = g->adjidx;
  int *gadjncy = g->adjncy;
  int *gadjwgt = g->adjwgt;
  int *gpro = g->pro;
  int *gvwgt = g->vwgt;
  for(_v = 0; _v < gnvtxs; _v++){
    istart = gadjidx[_v];
    iend = gadjidx[_v+1];
    printf("vertex %d with weight %d on P %d with adj: ", _v, gvwgt[_v], gpro[_v]);
    for(i = istart; i < iend; i++){
      printf("v%d, e%d; ", gadjncy[i], gadjwgt[i]);
    }
    printf("\n");
  }
*/

  /*******************************/
  /* stage one local refinement  */
  /*******************************/
  RCtrl.gain_fn   = &OneGain;  

  totnb_moves = 0;
  nb_moves    = 1;
  loops = 0;

  while(nb_moves != 0){    
    nb_moves = 0;  

    /* from overloaded */
    RCtrl.filter_fn = &OneFromFilter;
    HeapClean(&pHeap);
    for(i=0;i<nnpro;i++)
      HeapInsert(&pHeap,nexec[i]);

    while((from = HeapGetHead(&pHeap)) != -1){      
      if(!FILTEREXECFROM(&RCtrl,nexec[from]))
	break;
      HeapifyFrom(&RCtrl,from);
      if(HeapGetHead(RCtrl.heap) != -1){
	if((moves = Refine(&RCtrl)) != 0){	  
	  nb_moves += moves;
	}
      }else{
	HeapRemoveHead(&pHeap);
      }
    }
    
    /* to underloaded */
    RCtrl.filter_fn = &OneToFilter;

    HeapClean(&pHeap);
    
    for(i=0;i<nnpro;i++)
      HeapInsert(&pHeap,-nexec[i]);
  
    while((to = HeapGetHead(&pHeap)) != -1){
      if(!FILTEREXECTO(&RCtrl,nexec[to]))
	break;
      
      HeapifyTo(&RCtrl,to);
      if(HeapGetHead(RCtrl.heap) != -1){
	if((moves = Refine(&RCtrl)) != 0){
	  nb_moves += moves;
	}
      }else{
	HeapRemoveHead(&pHeap);
      }
    }
    totnb_moves += nb_moves;    
  }
  /******************************************************************************************/
  fprintf(stdout,"| %8d | execution time total : %10.2f | max : %10.2f | avg : %10.2f | im : %10.8f | tol : %10.8f |\n",
	  totnb_moves,
	  RCtrl.t,RCtrl.tmax,RCtrl.t/nnpro,nnpro*RCtrl.tmax/RCtrl.t,
	  RCtrl.imthreshold);
  /******************************************************************************************/  
#if DIFFUSE
  for(i=0;i<nnpro;i++)
    RCtrl.flow[i] = nexec[i] - RCtrl.tmean;

  totnb_moves = 0;  

  if(RCtrl.im>RCtrl.imthreshold){
    RCtrl.gain_fn   = &TwoGain;
  
    nb_moves    = 1;   
    loops = 0;    

    while(nb_moves != 0){      
      nb_moves = 0;
      
      /* from overloaded */
      RCtrl.filter_fn = &TwoFromFilter;

      HeapClean(&pHeap);

      for(i=0;i<nnpro;i++)
	HeapInsert(&pHeap,nexec[i]);

      while((from = HeapGetHead(&pHeap)) != -1){
	if(!FILTEREXECFROM(&RCtrl,nexec[from]))
	  break;
	HeapifyFrom(&RCtrl,from);
	if(HeapGetHead(RCtrl.heap) != -1){
	  if((moves = Refine(&RCtrl)) != 0){
	    nb_moves += moves;
	  }
	}else
	  HeapRemoveHead(&pHeap);
      }

      /* to underloaded */
      RCtrl.filter_fn = &TwoToFilter;

      HeapClean(&pHeap);
      
      for(i=0;i<nnpro;i++)
	HeapInsert(&pHeap,-nexec[i]);
      
      while((to = HeapGetHead(&pHeap)) != -1){
	if(!FILTEREXECTO(&RCtrl,nexec[to]))
	  break;
	
	HeapifyTo(&RCtrl,to);
	if(HeapGetHead(RCtrl.heap) != -1){
	  if((moves = Refine(&RCtrl)) != 0){	    
	    nb_moves += moves;
	  }
	}else
	  HeapRemoveHead(&pHeap);
	
	if(RCtrl.im<RCtrl.imthreshold)
	  break;
      }

      totnb_moves += nb_moves;      
    }
  }
  
#endif
  /******************************************************************************************/
  fprintf(stdout,"| %8d | execution time total : %10.2f | max : %10.2f | avg : %10.2f | im : %10.8f | tol : %10.8f |\n",
	  totnb_moves,
	  RCtrl.t,RCtrl.tmax,RCtrl.t/nnpro,nnpro*RCtrl.tmax/RCtrl.t,
	  RCtrl.imthreshold);
  /******************************************************************************************/

#if KL
  totnb_moves = 0;

  /* stage two kl refinement */
  /* try moves until cumulative deltaE < 0 */  
  RCtrl.undo_fn    = &KlUndo;
  RCtrl.filter_fn  = &KlFilter;
  RCtrl.gain_fn    = &KlGain;
  
  HeapClean(&pHeap);
    
  for(i=0;i<nnpro;i++)
    HeapInsert(&pHeap,nexec[i]);     
    
  while((from = HeapRemoveHead(&pHeap)) != -1){   
    (* RCtrl.undo_fn)(&RCtrl,UNDO_INI,NULL);
    HeapifyFrom(&RCtrl,from);
    if(HeapGetHead(RCtrl.heap) != -1){
      totnb_moves += RefineKl(&RCtrl);
    }
  }
  
  /******************************************************************************************/ 
  fprintf(stdout,"| %8d | execution time total : %10.2f | max : %10.2f | avg : %10.2f | im : %10.8f | tol : %10.8f |\n",
	  totnb_moves,
	  RCtrl.t,RCtrl.tmax,RCtrl.t/nnpro,nnpro*RCtrl.tmax/RCtrl.t,
	  RCtrl.imthreshold); 
  /******************************************************************************************/ 
#endif

  /******************************************************************************************/ 
  fprintf(stdout,"| level %2d | execution time total : %10.2f | max : %10.2f | avg : %10.2f | im : %10.8f | tol : %10.8f |\n",
	  level,RCtrl.t,RCtrl.tmax,RCtrl.t/nnpro,nnpro*RCtrl.tmax/RCtrl.t,
	  RCtrl.imthreshold);
  fprintf(stdout,"--------------------------------------------------------------------------------------------------------------------------\n");
  /******************************************************************************************/   

  debugExecNoPrint(&RCtrl);  
  VREF_Free(&RCtrl);
  U_free("execRefine error code 2.1\n",&(RCtrl.procs),&(RCtrl.proref),&(RCtrl.bnds),LEND);
#if MOVE_ONCE
  U_free("execRefine error code 2.2\n",&(RCtrl.mvtxs),LEND);
#endif
  
  MEM_Free(&mem);  
}

/**
 * \brief Apply moves of the move heap
 *
 * moves contained in the move heap (ctrl->heap) are applied if they 
 * pass the filter (ctrl->filter_fn) is a move is allowed everything is
 * updated.
 *
 * \param ctrl uncoarsening ctrl structure
 * \return number of reassigned vertices 
 */
int Refine(RefCtrl* ctrl){
  int v,idx,from,to,nb_moves = 0,dOflag;
  double deltaF,deltaT,deltaO;

  FILTER_FN* filter_fn = ctrl->filter_fn;
  
  Heap*  heap          = ctrl->heap;
  vRef** rvtxs         = ctrl->rvtxs;
  vRef*  rvtx;  
  
  while((v = HeapRemoveHead(heap)) != -1){
    rvtx   = rvtxs[v];
    idx    = rvtx->idx;
    to     = rvtx->to;
    from   = rvtx->from;
    deltaF = rvtx->deltaF;
    deltaT = rvtx->deltaT;
    deltaO = rvtx->deltaO;
    dOflag = rvtx->dOflag;        
    
    /********************************/
    /* reassignment passing filters */
    /********************************/
    if((* filter_fn)(ctrl,1,idx,from,to,deltaF,deltaT,deltaO,dOflag)){            
      /* update rinfo was deleted after that */
//printGraph(ctrl->g);
      MOVE_NOUNDO(ctrl,rvtx);           
//printf("move is made of vertex %d from p%d to p%d\n", idx, from, to); 
      nb_moves++;            
      continue;
    }
            
    /*************************************/
    /* not an interesting move remove it */
    /*************************************/
    HeapRemove(heap,v);
    AL_REM(rvtxs + v,rvtxs,ctrl->nrvtxs);            
  }
  return nb_moves;
}

/**
 * \brief Apply succesion of moves of the move heap that decrease the 
 * total execution time.
 *
 * moves contained in the move heap (ctrl->heap) are applied if they 
 * pass the filter (ctrl->filter_fn) is a move is allowed everything is
 * updated. Only moves or succession of moves that decrease 
 * the total execution time are applied
 *
 * \param ctrl uncoarsening ctrl structure
 * \return number of reassigned vertices 
 */
int RefineKl(RefCtrl* ctrl){
  int v,idx,from,to,nb_moves = 0,dOflag;
  double deltaF,deltaT,deltaO;

  UNDO_FN*     undo_fn = ctrl->undo_fn;
  FILTER_FN* filter_fn = ctrl->filter_fn;

  Heap*  heap          = ctrl->heap;
  vRef**  rvtxs        = ctrl->rvtxs;
  vRef*  rvtx;
  vRef   rvtx_cpy;    
  
  while((v = HeapRemoveHead(heap)) != -1){
    rvtx     = rvtxs[v];
    idx      = rvtx->idx;
    to       = rvtx->to;
    from     = rvtx->from;
    deltaF   = rvtx->deltaF;
    deltaT   = rvtx->deltaT;
    deltaO   = rvtx->deltaO;
    dOflag   = rvtx->dOflag;
    rvtx_cpy = *rvtx;        
    
    /********************************/
    /* reassignment passing filters */
    /********************************/
    if((* filter_fn)(ctrl,1,idx,from,to,deltaF,deltaT,deltaO,dOflag)){                    
      /* update */
      (* undo_fn)(ctrl,UNDO_UPDATE,rvtx);
      MOVE(ctrl,rvtx);            
//printf("in KL, a move is made of v%d from %d to %d\n", idx, from, to);
    }else{
      /*************************************/
      /* not an interesting move remove it */
      /*************************************/
      HeapRemove(heap,v);
      AL_REM(rvtxs + v,rvtxs,ctrl->nrvtxs);   
    }
    
    /***********************************************/
    /* undo condition, tried moves do not worth it */
    /***********************************************/
    switch((* undo_fn)(ctrl,UNDO_TEST,&rvtx_cpy)){
    case UNDO_UNDO:      
//printf("case UNDO_UNDO\n");
      UndoRecentMoves(ctrl);
      goto KLREFINE_END;
      break;
    /****************************************/
    /* undo condition, tried moved worth it */
    /****************************************/
    case UNDO_APPLY:                  
      nb_moves += ctrl->nb_undo;
      ctrl->nb_undo = 0;
      (* undo_fn)(ctrl,UNDO_INI,NULL);
      break;
    }    
  }
  
  /* undo moves that were not applied */
//printf("UNDO whatever\n");
  UndoRecentMoves(ctrl);

  /* we are done update recent move list and refinement list to be empty */
 KLREFINE_END:
  /* clear bnd links */
  for(v=0;v<ctrl->nrvtxs;v++)
    rvtxs[v]->pos = NULL;    
  ctrl->nrvtxs = 0;

  return nb_moves;
}
